class Solution {
    //正则表达式匹配
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        //创建dp表
        boolean[][] dp = new boolean[m + 1][n + 1];
        s = " " + s;
        p = " " + p;
        //初始化
        dp[0][0] = true;
        for(int j = 2; j <= n; j += 2){
            if(p.charAt(j) == '*'){
                dp[0][j] = true;
            }else{
                break;
            }
        }
        //填表
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(p.charAt(j) == '.'){
                    dp[i][j] = dp[i - 1][j - 1];
                }else if(p.charAt(j) == '*'){
                    dp[i][j] = dp[i][j - 2] || (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i)) && dp[i - 1][j];
                }else if(s.charAt(i) == p.charAt(j)){
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    //交错字符串
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        //先处理不能组成的情况
        if(m + n != s3.length()) return false;
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int j = 1; j <= n; j++){
            if(s2.charAt(j) == s3.charAt(j)) dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++){
            if(s1.charAt(i) == s3.charAt(i)) dp[i][0] = true;
            else break;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = (s1.charAt(i) == s3.charAt(i + j) && dp[i - 1][j])
                        || (s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

    //两个字符串的最小ASCII删除和
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(chs1[i - 1] == chs2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + chs1[i - 1];
                dp[i][j] = Math.max(Math.max(dp[i - 1][j], dp[i][j - 1]), dp[i][j]);
            }
        }
        int sum = 0;
        for(int i = 0; i < m; i++){
            sum += chs1[i];
        }
        for(int j = 0; j < n; j++){
            sum += chs2[j];
        }
        return sum - 2*dp[m][n];
    }

    //最长重复子数组
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                max = Math.max(dp[i][j], max);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.isMatch("aabc", "abad");
        solution.isInterleave("aabc", "abad", "aabadabc");
    }
}